package com.acwing.partition11;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/24 9:11
 */
public class AC1081度的数量 {

    private static final int N = 35;
    private static int[][] dp = new int[N][N];
    private static int K, B;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        init();
        int x = Integer.parseInt(s[0]), y = Integer.parseInt(s[1]);
        //k指定了转换成b进制后的b-1有多少个
        K = Integer.parseInt(reader.readLine());
        B = Integer.parseInt(reader.readLine());
        writer.write((resolve(y) - resolve(x - 1)) + "\n");
        writer.flush();
    }

    private static void init() {
        //初始化组合数
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = j == 0 ? 1 : dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
    }

    private static int resolve(int num) {
        //如果上边界是0，直接返回0
        if (num == 0) return 0;
        //将num转换成b进制，并逆序存储
        List<Integer> nums = new ArrayList<>();
        while (num != 0) {
            nums.add(num % B);
            num /= B;
        }
        //used记录遍历当前位时，在当前位之前已经用过了多少个1，此时还能用的1的数量就是K-used
        int answer = 0, used = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            int x = nums.get(i);
            if (x > 0) {
                //x的上界大于0，左边的分支可以填0
                answer += dp[i][K - used];
                if (x == 1) {
                    //右边分支等于1，可以继续讨论
                    used++;
                    if (used > K) break;
                } else {
                    //x的上界大于1，且如果还能填1的话，左边的分支填1
                    if (K - used - 1 >= 0) answer += dp[i][K - used - 1];
                    //右边的分支只能填0或1，不符合条件，直接break
                    break;
                }
            }
            if (i == 0 && used == K) answer++;
        }
        return answer;
    }
}
